The Batcher-banyan network is a self-routing network which is capable of synchronously routing packets of data in time slots from a set of input terminals to a set of output terminals without centralized control. The routing through the network is determined by an address contained in the header of each packet.
The Batcher-banyan network comprises a Batcher sorting network, followed by a banyan routing network. The function of the Batcher sorting network is to arrange incoming packets in ascending or descending order according to their destination addresses. The function of the banyan network is to route the presorted packets to their destination output terminals.
The banyan network can route a data packet from any input terminal to any destination terminal, but may suffer from internal packet congestion, in the sense that two or more packets may be routed through the same internal link at the same time. However, the banyan network is internally non-blocking if in a particular time slot no more than one incoming packet is addressed to each banyan output and the packets are arranged in ascending or descending order when they arrive at the banyan inputs. Therefore it is possible to construct a non-blocking network by combining a Batcher sorting network and a banyan routing network. An example of a switching system in which a non-blocking selfrouting Batcher-banyan network is utilized can be found in U.S. Pat. No. 4,782,478. The above-identified patent is incorporated herein by reference.
The Batcher-banyan network may be built from small switching cells. By using VLSI technology many of these cells may be implemented in a single VLSI chip. Many applications require the Batcher-banyan network to operate at very high speeds such as 100 megabits/sec. It is often the case that signal propagation delays in the electrical connections between individual chips comprising a network such as the Batcher-banyan network contribute more to processing delays than signal propagation delays within individual IC chips.
It has previously been suggested that "between chip signal propagation delays" in complex networks can be reduced by forming the network from chips arranged in adjoining horizontal and vertical stacks (see, e.g., Donald K. Wilson, "Topological Aspects of Systems Partitioning," pp. 148-154, Vol. 3 "Design Theory and Practice", Proceedings of the International Conference on Design Policy, July 1982).
In view of the above, it is an object of the present invention to provide a switching cell for a packet switching network such as a banyan network, which switching cell enables a packet switching network to be implemented in three dimensions by interconnected horizontal and vertical stacks of chips.